package heap;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.junit.Test;

public class Heap {
	@Test
	public void fun() {
		Heap p = new Heap();
		p.Push(20);
		p.Push(30);
		p.Push(15);
		System.out.println(p.Top());
		p.Push(90);
		p.Push(35);
		System.out.println(p.Top());
		p.Pop();
		System.out.println(p.Top());
	}
	
	private List<Integer> heapArray;
	public Heap() {
		super();
		this.heapArray = new ArrayList();
	}
	//添加元素进堆 
	public void Push(Integer x) {
		heapArray.add(x);
		trickleUp(heapArray.size()-1);
	}
	//删除元素
	public void Pop() {
		heapArray.set(0, heapArray.get(heapArray.size()-1));
		heapArray.remove(heapArray.size()-1);
		trickleDown(0);
	}
	//取出根数据
	public Integer Top() {
		return heapArray.get(0);
	}
	//判断是否为空
	public boolean isEmpty() {
		if(Top() == null) {
			return true;
		}
		return false;
	}
	//向上渗透
	public void trickleUp(int index) {
		int parent = (index-1) / 2;
		Integer bottom = heapArray.get(index);
		while(index > 0 && heapArray.get(parent) < bottom) {
			heapArray.set(index, heapArray.get(parent));
			index = parent;
			parent = (parent - 1) / 2;
		}
		heapArray.set(index, bottom);
	}
	//向下渗透
	public void trickleDown(int index) {
		Integer top = heapArray.get(0);
		int lagerChild;
		while(index < heapArray.size()/2) {
			int leftChild = index * 2 + 1;
			int rightChild = index * 2 + 2;
			if(rightChild < heapArray.size() && heapArray.get(leftChild) < heapArray.get(rightChild)) {
				lagerChild = rightChild;
			}else {
				lagerChild = leftChild;
			}
			if(top >= heapArray.get(lagerChild)) {
				break;
			}
			heapArray.set(index, heapArray.get(lagerChild));
			index = lagerChild;
		}
		heapArray.set(index, top);
	}
}
